package stringMatch;

public class KMP {
    private String pattern;
    private int[][] next;

    public KMP(String pattern) {
        this.pattern = pattern;
        next = new int[2][pattern.length()];
        next[0][0] = pattern.charAt(0);
        // 构造next数组
        for (int i = 2; i <= pattern.length(); i++) {
            int count = 0;
            String subString = pattern.substring(0, i);
            int tmp = 1;
            // 计算前后缀的匹配数
            while (tmp < i) {
                if (subString.substring(0, tmp)
                        .equals(subString.substring(subString.length() - tmp, subString.length()))) {
                    count = tmp;
                }
                tmp++;
            }
            next[0][i - 1] = pattern.charAt(i - 1);
            next[1][i - 1] = count;
        }
    }

    public int search(String text) {
        int tmp = 0;
        int i;
        for (i = 0; i < text.length(); i++) {
            if (text.charAt(i) != pattern.charAt(tmp)) {
                tmp = next[1][tmp];
                if (text.charAt(i) != pattern.charAt(tmp)) {
                    tmp = 0;
                }else{
                    tmp++;
                }
            } else {
                tmp++;
                if (tmp == pattern.length()) {
                    return i-pattern.length()+1;
                }
            }
        }
        return -1;
    }

    public String getPattern() {
        return pattern;
    }

    public void setPattern(String pattern) {
        this.pattern = pattern;
    }

    public int[][] getNext() {
        return next;
    }

    public void setNext(int[][] next) {
        this.next = next;
    }
}